import java.util.ArrayList;
import java.util.List;

class Solution {
    //N皇后
    public List<List<String>> ret;
    public List<String> path;
    public boolean[] col;
    public boolean[] dig1;//主对角线
    public boolean[] dig2;//副对角线
    public List<List<String>> solveNQueens(int n) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        col = new boolean[n];
        dig1 = new boolean[2 * n];
        dig2 = new boolean[2 * n];
        dfs(0, n);
        return ret;
    }
    public void dfs(int index, int n){
        //递归出口
        if(index == n){
            ret.add(new ArrayList<>(path));
            return;
        }
        //函数体
        for(int i = 0; i < n; i++){
            if(col[i] == false && dig1[i - index + n] == false && dig2[index + i] == false){
                StringBuilder stringBuilder = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if(j != i){
                        stringBuilder.append(".");
                    }else {
                        stringBuilder.append("Q");
                    }
                }

                //递归
                path.add(stringBuilder.toString());
                col[i] = true;
                dig1[i - index + n] = true;
                dig2[index + i] = true;
                dfs(index + 1, n);

                //回溯
                path.remove(path.size() - 1);
                col[i] = false;
                dig1[i - index + n] = false;
                dig2[index + i] = false;
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solveNQueens(1);
    }
}